package com.graph.base;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import com.graph.util.NMIMeasure;

public abstract class GraphBase extends Modularity implements Serializable {

	private static final long serialVersionUID = 1L;
	
	private List<Set<Integer>> nowAnswer = new ArrayList<Set<Integer>>();
	
	private List<Set<Integer>> standardAnswer = new ArrayList<Set<Integer>>();
	/**
	 *存储图中所有的点，key是点的名称
	 */
	private Map<String, VertexInterface> vertices;
	/**
	 * 存储所有的点
	 */
	private  List<VertexInterface> verticesList = null;
	/**
	 * 所有边的数目（双向边数目）
	 */
	private int edgeCount;

	public GraphBase() {
		vertices = new LinkedHashMap<>();
	}

	public void addVertex(String vertexLabel) {
		vertices.put(vertexLabel, new VertexImpl(vertexLabel));
	}

	public boolean addEdge(String begin, String end, Integer edgeWeight) {
		boolean result = false;
		VertexInterface beginVertex = vertices.get(begin);
		VertexInterface endVertex = vertices.get(end);
		if (beginVertex != null && endVertex != null){
			result = beginVertex.connect(endVertex, edgeWeight);
		}
		if (result){
			edgeCount++;
		}
		return result;
	}

	public boolean addEdge(String begin, String end) {
		return addEdge(begin, end, 0);
	}

	public boolean isEmpty() {
		return vertices.isEmpty();
	}

	public int getNumberOfVertices() {
		return vertices.size();
	}

	public int getNumberOfEdges() {
		return edgeCount;
	}

	public void clear() {
		vertices.clear();
		edgeCount = 0;
	}

	
	public  List<VertexInterface> getVerticesList(){
		if(verticesList == null){
			List<VertexInterface> list = new ArrayList<VertexInterface>();
			Iterator<Entry<String, VertexInterface>> iter = this.getVertices().entrySet().iterator();
			while(iter.hasNext()){
				Entry<String,VertexInterface> entry = iter.next();
				VertexInterface value = entry.getValue();
				list.add(value);
			}
			return list;
		}else{
			 return verticesList;
		}
	}

	protected void resetVertices() {
		Iterator<VertexInterface> vertexIterator = vertices.values().iterator();
		while (vertexIterator.hasNext()) {
			VertexInterface nextVertex = vertexIterator.next();
			nextVertex.setCost(0);
			nextVertex.unVisit();
		}
	}

	public Map<String, VertexInterface> getVertices() {
		return this.vertices;
	}

	/**
	 * 返回所给点图中形成的边（2倍）
	 * @Description:TODO
	 * @param graph
	 * @return
	 * @author: wujiang
	 * @time:2017-1-12 下午3:42:44
	 */
	public List<Edge> getEdge(List<VertexInterface> graph){
		List<Edge> edges = new ArrayList<Edge>();
		if(graph != null){
			for (VertexInterface vertexInterface : graph) {
				List<Edge> list = vertexInterface.getEdgeList();
				for (Edge edge : list) {
					VertexInterface vertexInterfaceEnd = edge.getEndVertex();
					if(graph.contains(vertexInterfaceEnd)){
						edges.add(edge);
					}
				}
			}
		}
		return edges;
	}

	public Set<VertexInterface> getNeighbors(VertexInterface aim){
		if(aim.getNeighors() != null && aim.getNeighors().size() != 0){
			return aim.getNeighors();
		}
		Set<VertexInterface> around = new HashSet<VertexInterface>();
		Iterator<VertexInterface> iter = aim.getNeighborInterator();
		while(iter.hasNext()){
			VertexInterface temp = iter.next();
			around.add(temp);
		}
		aim.setNeighors(around);
		return around;
	}

    public Boolean isContain(List<Set<VertexInterface>> list, Set<VertexInterface> set1){
    	for (Set<VertexInterface> set2 : list) {
			if(set2.size() == set1.size()){
				if(set2.equals(set1)){
					return true;
				}
			}else{
				return false;
			}
		}
		return false;
    }

	
	public boolean isNeighbor(VertexInterface vertexInterface1,VertexInterface vertexInterface2){
		Set<VertexInterface> sets = getNeighbors(vertexInterface1);
		for (VertexInterface vertexInterface : sets) {
			if(vertexInterface.equals(vertexInterface2) || vertexInterface == vertexInterface2){
				return true;
			}
		}
		return false;
	}
    
	public double modularityQ(Map<VertexInterface,Integer> vertexInterfaceMap){
		List<VertexInterface> allvers = getVerticesList();
		Integer verNum = allvers.size();
		double q = 0.0;
		//双向边的总数
		int m2 = getNumberOfEdges();
		for (int i = 0; i < verNum; i++) {
			for (int j = 0; j < verNum; j++) {
				if(i != j){
					VertexInterface v1 = allvers.get(i);
					VertexInterface v2 = allvers.get(j);
					Integer t1 = vertexInterfaceMap.get(v1);
					Integer t2 = vertexInterfaceMap.get(v2);
					if(t1 == null || t2 == null) {
						continue;
					}
					if(vertexInterfaceMap.get(v1).equals(vertexInterfaceMap.get(v2))){
						double de = v1.getDegree() * v2.getDegree();
						double l = de / m2;
						if(isNeighbor(v1, v2)){
							q = q + 1 - l;
						}else{
							q = q - l;
						}
					}
				}
			}
		}
		return q / m2;
	}

	public Integer getEdgesTwoVertex(VertexInterface v1,VertexInterface v2){
		return edgeCount;
	}

	
	public void  initStandAnswer(String[] clusters){
		List<Set<Integer>> answer = getStandardAnswer();
		for (int i = 0; i < clusters.length; i++) {
			Set<Integer> cluster = new HashSet<Integer>();
			String[] elements = clusters[i].split(",");
			for (int j = 0; j < elements.length; j++) {
				cluster.add(Integer.parseInt(elements[j]));
			}
			answer.add(cluster);
		}
	}

	public List<Set<Integer>> getStandardAnswer() {
		return standardAnswer;
	}

	public void setStandardAnswer(List<Set<Integer>> standardAnswer) {
		this.standardAnswer = standardAnswer;
	}

	public List<Set<Integer>> getNowAnswer() {
		return nowAnswer;
	}

	public void setNowAnswer(List<Set<Integer>> nowAnswer) {
		this.nowAnswer = nowAnswer;
	}
	
	public void initNowAnswer(List<Set<VertexInterface>> result ){
		List<Set<Integer>> nowAnswer = getNowAnswer();
		for (Set<VertexInterface> vertexInterfaceSet : result) {
			Set<Integer> cluster = new HashSet<Integer>();
			for (VertexInterface vertexInterface : vertexInterfaceSet) {
				cluster.add(Integer.parseInt(vertexInterface.getName()));
			}
			nowAnswer.add(cluster);
		}
	}

	public double getNMI() {
		Map<Integer, Integer> maps = new HashMap<Integer, Integer>(16);
		List<Set<Integer>> answer = getStandardAnswer();
		for (int i = 0; i < answer.size(); i ++) {
			Set<Integer> cluster = answer.get(i);
			for (Integer j : cluster) {
				maps.put(j, i);
			}
		}
		List<Set<Integer>> nanswer = getNowAnswer();
		List<List<Integer>> lists = new ArrayList<List<Integer>>();
		for (int i = 0; i < nanswer.size(); i++) {
			Set<Integer> cluster1 = nanswer.get(i);
			List<Integer> list = new ArrayList<Integer>();
			for (Integer j : cluster1) {
				list.add(maps.get(j));
			}
			lists.add(list);
		}
		return NMIMeasure.nmiPartition(getNowAnswer(), getStandardAnswer(), getNumberOfVertices());
	}
}